package leetcode.year2021.month10;

import java.util.HashMap;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 */
public class _25_01BuildTree105 {
  public static void main(String[] args) {
    int[] preorder = new int[]{3,9,20,15,7};
    int[] inorder = new int[]{9,3,15,20,7};

    buildTree(preorder,inorder);
  }
  public static TreeNode buildTree(int[] preorder, int[] inorder) {
    // 思路： 先序遍历的第一个节点是根节点， 在中序遍历中找到该值，中序遍历的左边，是根节点的左子树，右边是右子树
    // 使用递归的思路，找到第一个节点的左子树和右子树，然后递归调用

    HashMap intMap = new HashMap<Integer,Integer>();
    for (int i = 0; i < inorder.length; i++) {
      intMap.put(inorder[i],i);
    }

    return buildTreeDfs(intMap, 0,inorder.length-1,0, inorder.length-1, preorder, inorder);
  }

  private static TreeNode buildTreeDfs(HashMap<Integer,Integer> intMap, int preStartIndex, int preEndIndex, int midStartIndex, int midEndIndex, int[] preorder, int[] inorder) {
    TreeNode root = new TreeNode(preorder[preStartIndex]);
    //拿到中序遍历的该值的位置
    Integer index = intMap.get(preorder[preStartIndex]);
    // 中序遍历  index左边位置的序号有， midStartIndex - index-1
    // 那相应的先序遍历的对应的序号为， preStartIndex+1 - （preStartIndex + index - midStartIndex）

    if (index == midStartIndex){
      root.left = null;
    } else {
      root.left = buildTreeDfs(intMap,preStartIndex+1, preStartIndex + index - midStartIndex, midStartIndex,index-1, preorder, inorder);
    }

    // 中序遍历，index 右边的位置的序号有 index + 1   -  midEndIndex
    // 先序遍历,     preStartIndex+1    -  preStartIndex + midEndIndex - index
    if (index == midEndIndex){
      root.right = null;
    } else {
      root.right = buildTreeDfs(intMap,preStartIndex+1+index-midStartIndex, preStartIndex + midEndIndex -midStartIndex, index + 1, midEndIndex, preorder, inorder);
    }

    return root;
  }


  public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }


  /**
   * 105. 从前序与中序遍历序列构造二叉树
   * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
   *
   *
   *
   * 示例 1:
   *
   *
   * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
   * Output: [3,9,20,null,null,15,7]
   * 示例 2:
   *
   * Input: preorder = [-1], inorder = [-1]
   * Output: [-1]
   *
   *
   * 提示:
   *
   * 1 <= preorder.length <= 3000
   * inorder.length == preorder.length
   * -3000 <= preorder[i], inorder[i] <= 3000
   * preorder 和 inorder 均无重复元素
   * inorder 均出现在 preorder
   * preorder 保证为二叉树的前序遍历序列
   * inorder 保证为二叉树的中序遍历序列
   */
}
